package com.lw.leetcode.node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 652. 寻找重复的子树
 *
 * @Author liw
 * @Date 2021/5/12 14:18
 * @Version 1.0
 */
public class FindDuplicateSubtrees {

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<Integer, List<TreeNode>> all = new HashMap<>();
        Map<Integer, List<TreeNode>> repet = new HashMap<>();
        find(root, all, repet);
        List<TreeNode> list = new ArrayList<>();
        for (Map.Entry<Integer, List<TreeNode>> entry : repet.entrySet()) {
            list.addAll(entry.getValue());
        }
        return list;
    }


    private void find(TreeNode node, Map<Integer, List<TreeNode>> all, Map<Integer, List<TreeNode>> repet) {
        if (node == null) {
            return;
        }
        int val = node.val;
        List<TreeNode> allList = all.get(val);
        List<TreeNode> repetList = repet.get(val);
        if (allList == null && repetList == null) {
            allList = new ArrayList<>();
            allList.add(node);
            all.put(val, allList);
            find(node.left, all, repet);
            find(node.right, all, repet);
        } else {
            if (repetList != null) {
                for (TreeNode treeNode : repetList) {
                    if (check(treeNode, node)) {
                        find(node.left, all, repet);
                        find(node.right, all, repet);
                        return;
                    }
                }
            }
            if (allList != null) {
                for (int i = 0; i < allList.size(); i++) {
                    TreeNode treeNode = allList.get(i);
                    if (check(treeNode, node)) {
                        allList.remove(i);
                        if (repetList != null) {
                            repetList.add(node);
                        } else {
                            repetList = new ArrayList<>();
                            repetList.add(node);
                            repet.put(val, repetList);
                        }
                        find(node.left, all, repet);
                        find(node.right, all, repet);
                        return;
                    }
                }
                allList.add(node);
            } else {
                allList = new ArrayList<>();
                allList.add(node);
                all.put(val, allList);
            }
            find(node.left, all, repet);
            find(node.right, all, repet);
        }
    }

    private boolean check (TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        if (a.val == b.val) {
            return check(a.left, b.left) && check(a.right, b.right);
        }
        return false;
    }

}
